import java.util.HashMap;
import java.util.Map;

class Solution {
    public String minWindow(String s, String t) {
        if(s.length() < t.length()){
            return "";
        }
        //建立哈希表，将t中的字符都存起来
        Map<Character, Integer> mapT = new HashMap<>();
        for(int i = 0; i < t.length(); i++){
            char ch = t.charAt(i);
            mapT.put(ch, mapT.getOrDefault(ch, 0) + 1);
        }
        int left = 0;
        int right = 0;
        int count = 0;
        String str = s;
        Map<Character, Integer> mapS = new HashMap<>();
        while(right < s.length()){
            //进窗口 维护count
            char ch = s.charAt(right);
            mapS.put(ch, mapS.getOrDefault(ch, 0) + 1);
            if(mapS.get(ch) <= mapT.getOrDefault(ch, 0)) {
                count++;
            }
            //出窗口 维护count
            while(count >= t.length()){
                //更新结果
                if(count == t.length()){
                    if(str.length() > (right - left + 1))
                        str = s.substring(left, right + 1);
                }
                char key = s.charAt(left);
                int value = mapS.get(key);
                if(value <= mapT.getOrDefault(key, 0)){
                    count--;
                }
                if(value > 1){
                    mapS.put(key, value - 1);
                }else{
                    mapS.remove(key);
                }
                left++;
            }
            right++;
        }
        return str;
    }
}
